/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder 先序
 * @param {number[]} inorder 中序
 * @return {TreeNode}
 */

var buildTree = function(preorder, inorder) {
    let length = inorder.length,
        root_value = preorder[0];

    if(length===0)return null;

    let root = new TreeNode(root_value);

    if(length===1)return root;

    // slice:[s,e)
    let root_index_io = getValueIndex(inorder, root_value);
    if(root_index_io === null)return null;

    let left_arr_io = inorder.slice(0, root_index_io);
    let right_arr_io = inorder.slice(root_index_io+1);

    let left_arr_po = preorder.slice(1, root_index_io+1);
    let right_arr_po = preorder.slice(root_index_io+1);

    //console.log(left_arr_io.length, left_arr_po.length);

    root.left = buildTree(left_arr_po, left_arr_io);
    root.right = buildTree(right_arr_po, right_arr_io);

    return root;

};

function getValueIndex(arr, target) {
    let s = 0,
        length = arr.length;
    for( ; s<length; s++){
        if(arr[s] === target){
            return s;
        }
    }
    return null;
}

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}